ขั้นตอนวิธี ของ Dynamic time warping

เป้าหมายของไดนามิกไทม์วอร์ปปิง คือ เพื่อเปรียบเทียบลำดับที่ขึ้นอยู่กับเวลาสองชุด

X := ( x 1 , x 2 , . . . , x N ) {\displaystyle X:=(x_{1},x_{2},...,x_{N})\,} ด้วยความยาว N {\displaystyle N\,} ซึ่งเป็นจำนวนเต็ม Y := ( y 1 , y 2 , . . . , y M ) {\displaystyle Y:=(y_{1},y_{2},...,y_{M})\,} ด้วยความยาว M {\displaystyle M\,} ซึ่งเป็นจำนวนเต็ม

โดยลำดับเหล่านี้อาจจะเป็นสัญญาณที่ไม่ต่อเนื่อง (อนุกรมเวลา) หรือ ลำดับของลักษณะเฉพาะ (feature) ที่ถูกสร้างขึ้นตามช่วงเวลา กำหนดให้ปริภูมิของลักษณะเฉพาะแทนด้วย F {\displaystyle F\,} ดังนั้น x n , y m ∈ F {\displaystyle x_{n},y_{m}\in F} สำหรับ n ∈ [ 1 : N ] {\displaystyle n\in [1:N]} และ m ∈ [ 1 : M ] {\displaystyle m\in [1:M]} เพื่อที่จะเปรียบเทียบลักษณะเฉพาะ x , y ∈ F {\displaystyle x,y\in F} จึงจำเป็นที่จะต้องคำนวณต้นทุนเฉพาะส่วน (local cost measure) หรือเรียกอีกอย่างได้ว่า การคำนวณระยะทางเฉพาะส่วน (local distance measure) ซึ่งนิยามได้เป็นฟังก์ชัน c : F × F → R ⩾ 0 {\displaystyle c:F\times F\rightarrow R\geqslant 0} ซึ่งโดยทั่วไป c ( x , y ) {\displaystyle c(x,y)\,} จะมีค่าน้อย ถ้า x {\displaystyle x\,} และ y {\displaystyle y\,} มีความคล้ายกันมาก ซึ่งสำหรับแต่ละคู่ของลำดับทั้งสอง นำไปสร้าง เมทริกซ์ต้นทุน (cost matrix) C ∈ R N × M {\displaystyle C\in R^{N\times M}} นิยามด้วย C ( n , m ) := c ( x n , y m ) {\displaystyle C(n,m):=c(x_{n},y_{m})\,} ดังรูป

เมทริกซ์ต้นทุนของลำดับ X {\displaystyle X} และ Y {\displaystyle Y} บริเวณสีเข้มในเมทริกซ์แสดงถึงส่วนที่มีต้นทุนต่ำ และบริเวณสีอ่อนแสดงถึงส่วนที่มีต้นทุนสูง

โดยเป้าหมายต่อไปคือการหาวิถีการปรับแนวระหว่าง X {\displaystyle X\,} และ Y {\displaystyle Y\,} ที่มีต้นทุนรวมน้อยที่สุด โดยปกติแล้ว วิถีการปรับแนว จะวิ่งไปตามทางที่ต้นทุนต่ำภายในเมทริกซ์ต้นทุน ด้วยรูปแบบดังนี้

เส้นทางบิดเบือน ( N , M ) {\displaystyle (N,M)\,} เป็นลำดับ p = ( p 1 , . . . , p L ) {\displaystyle p=(p_{1},...,p_{L})\,} และ p l = ( n l , m l ) ∈ [ 1 : N ] × [ 1 : M ] {\displaystyle p_{l}=(n_{l},m_{l})\in [1:N]\times [1:M]} สำหรับ l ∈ [ 1 : L ] {\displaystyle l\in [1:L]} จะสนใจเงื่อนไขดังต่อไปนี้

  1. เงื่อนไขขอบเขต (Boundary condition) : p 1 = ( 1 , 1 ) {\displaystyle p_{1}=(1,1)\,} และ p L = ( N , M ) {\displaystyle p_{L}=(N,M)\,}
  2. เงื่อนไขทางเดียว (Monotonicity condition) : n 1 ⩽ n 2 ⩽ . . . ⩽ n L {\displaystyle n_{1}\leqslant n_{2}\leqslant ...\leqslant n_{L}} และ m 1 ⩾ m 2 ⩾ . . . ⩾ m L {\displaystyle m_{1}\geqslant m_{2}\geqslant ...\geqslant m_{L}}
  3. เงื่อนไขขนาดการเดิน (step size condition) : p l + 1 − p l ∈ { ( 1 , 0 ) , ( 0 , 1 ) , ( 1 , 1 ) } {\displaystyle p_{l+1}-p_{l}\in \{(1,0),(0,1),(1,1)\}} สำหรับ l ∈ [ 1 : L − 1 ] {\displaystyle l\in [1:L-1]}

ซึ่งจะได้ตัวอย่างของเส้นทางบิดเบือนแบบต่างๆภายใต้เงื่อนไขดังรูป

เส้นทางการบิดเบือนภายใต้เงื่อนไขแบบต่างๆ

โดยต้นทุนทั้งหมดของเส้นทางบิดเบือน p {\displaystyle p\,} ระหว่าง X {\displaystyle X\,} และ Y {\displaystyle Y\,} ซึ่งเกี่ยวเนื่องกับการวัดต้นทุนเฉพาะส่วน c {\displaystyle c\,} จะถูกนิยามด้วย
c p ( X , Y ) := ∑ l = 1 L c ( x n l , y n l ) {\displaystyle c_{p}(X,Y):=\sum _{l=1}^{L}c(x_{n_{l}},y_{n_{l}})}

สำหรับ เส้นทางบิดเบือนที่เหมาะสมระหว่าง X {\displaystyle X\,} และ Y {\displaystyle Y\,} คือระยะทางบิดเบือน p ′ {\displaystyle p'\,} ซึ่งมีต้นทุกต่ำที่สุดเมื่อเทียบกับเส้นทางบิดเบือนทั้งหมดที่เป็นไปได้ ระยะทางไดนามิกไทม์วอร์ปปิง D T W ( X , Y ) {\displaystyle DTW(X,Y)\,} ระหว่าง X {\displaystyle X\,} และ Y {\displaystyle Y\,} จะถูกนิยามเป็นต้นทุนทั้งหมดของ p ′ {\displaystyle p'\,} โดย

D T W ( X , Y ) {\displaystyle DTW(X,Y)\,} := c p ′ ( X , Y ) {\displaystyle :=c_{p'}(X,Y)\,}
  = m i n { c p ( X , Y ) | p {\displaystyle =min\{c_{p}(X,Y)|p\,} เป็นเส้นทางบิดเบือน ( N , M ) } {\displaystyle (N,M)\}\,}


ซึ่งสุดท้ายแล้วจะได้ระยะทางบิดเบือนที่เหมาะสมดังรูป

เส้นสีขาวในรูปแสดงถึงเส้นทางไดนามิกไทม์วอร์ปปิงบนเมทริกซ์ต้นทุน

ใกล้เคียง